//package _dp_base;
//
///**
// * 221. 最大正方形
// */
//public class No221 {
//    private char[][] matrix;
//    private int[][] cache;
//
//    public int maximalSquare(char[][] matrix) {
//        this.matrix = matrix;
//        int m = matrix.length;
//        int n = matrix[0].length;
//        cache = new int[m][n];
//        for (int i = 0; i < m; i++) {
//            for (int j = 0; j < n; j++) {
//                cache[i][j] = -1;
//            }
//        }
//        int side = dfs(m - 1, n - 1);
//        return side * side;
//    }
//
//    private int dfs(int i, int j) {
//        if (i < 0 || j < 0) return 0;
//        else if (cache[i][j] != -1) return cache[i][j];
//        else if (matrix[i][j] == '1')
//            return cache[i][j] = Math.min(dfs(i - 1, j - 1), Math.min(dfs(i, j - 1), dfs(i - 1, j))) + 1;
//        else if (matrix[i][j] == '0')
//            return cache[i][j] = Math.max(dfs(i - 1, j - 1), Math.max(dfs(i, j - 1), dfs(i - 1, j)));
//    }
//}
